import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.PropertyResourceBundle;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2023-03-09
 * Time: 13:25
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Day20 {
    //671.二叉树中第二小的节点 - 标记
    public int find(TreeNode root, int val){
        //1.寻找特殊返回值，null时
        if (root == null){
            return -1;
        }
        //2.寻找特殊返回值2，当只有三节点时
        if (root.val > val){
            return root.val;
        }
        //3.将结果一般化，寻找递归原则,需要保留根节点的val值
        int left = find(root.left, val);
        int right = find(root.right, val);

        //4.返回值判断
        if (left > val && right > val){
            return Math.min(left, right);
        }
        return Math.max(left,right);
    }
    public int findSecondMinimumValue(TreeNode root) {
        return find(root, root.val);
    }

    //700.二叉搜索树中的搜索
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null){
            return null;
        }
        if (root.val == val){
            return root;
        }
        if (root.val < val){
            return searchBST(root.right, val);
        }else{
            return searchBST(root.left, val);
        }
    }
}
//703.数据流中第K大的值
class KthLargest {
    private int k;
    private PriorityQueue<Integer> pq;
    public KthLargest(int k, int[] nums) {
        this.k = k;
        pq = new PriorityQueue<>(k);
        for(int i: nums){
            add(i);
        }
    }

    public int add(int val) {
        if (pq.size() < k){
            pq.offer(val);
        }else if (pq.peek() < val){
            pq.poll();
            pq.offer(val);
        }
        return pq.peek();
    }
    //783.二叉搜索树节点间最小距离 - 标记
    private int min = 100001;
    private TreeNode pre = null;
    public void minDiff(TreeNode root){
        if (root == null){
            return;
        }
        minDiff(root.left);
        if (pre != null){
            min = Math.min(root.val - pre.val, min);
        }
        pre = root;
        minDiff(root.right);
    }
    public int minDiffInBST(TreeNode root) {
        minDiff(root);
        return min;
    }
    //872.叶子相似的树 - 标记不能用数组
    public void leafArray(TreeNode root, List<Integer> list){
        if (root == null){
            return;
        }
        if (root.left == null && root.right == null){
            list.add(root.val);
        }
        leafArray(root.left, list);
        leafArray(root.right, list);
    }
    public boolean leafSimilar(TreeNode root1, TreeNode root2){
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();

        leafArray(root1, list1);
        leafArray(root2, list2);

        if (list1.size() != list2.size()){
             return false;
        }
        for (int i = 0; i < list1.size(); i++) {
            if (list1.get(i) != list2.get(i)){
                return false;
            }
        }
        return true;
    }
    //938.二叉搜索树的范围和
    public int rangeSumBST(TreeNode root, int low, int high) {
        if (root == null){
            return 0;
        }

        if (root.val > high){
            return rangeSumBST(root.left, low, high);
        }else if (root.val < low){
            return rangeSumBST(root.right, low, high);
        }else{
            return root.val + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
        }
    }
}
